Questioning Information Cost
| July 12, 2013 | Posted by Winston Ewert under Intelligent Design |
Di.. Eb.., or Dieb, on the blog DiEbLog, has posted a number of questions, relating to the paper A General Theory of Information Cost Incurred by Successful Search. He raises a number of questions and objections to the paper.
Firstly, Dieb objects that the quasi-Bayesian calculation on Page 56 is incorrect, although it obtains the correct result. However, the calculation is called a quasi-Bayesian calculation because it engages in hand-waving rather than presenting a rigorous proof. The text in question is shortly after a theorem and is intended to explicate the consequences of that theorem rather than rigorously prove its result. The calculation is not incorrect, but rather deliberately oversimplified.
Secondly, Dieb objects that many quite different searches can be constructed which are represented by the same probability measure. However, if searches were represented as a mapping from the previously visited points to a new point (as in Wolpert and Macready’s original formulation), algorithms which derive the same queries in different ways will be represented the same way. Giving multiple searches the same representation is neither avoidable nor inherently problematic.
Thirdly, Dieb objects that a search will be biased by the discriminator towards selecting elements in the target, not a uniform distribution. However, Dieb’s logic depends on assuming that we have a good discriminator. As the paper states, we do not assume this to be the case. If choosing a random search, we cannot assume that we have a good discriminator (or any other component). The search for the search assumes that we have no prior information, not even the ability to identify points in the target.
Fourthly, Dieb doesn’t see the point in the navigator’s output as it is can be seen as just the next element of the search path. However, the navigator produces information like a distance to the target. The distance will be helpful in determining where to query, but it does not determine the next element of the search path. So it cannot be seen as just the next element of the search path.
Fifthly, Dieb objects that the inspector is treated inconsistently. However, the output of the inspector is not inconsistent but rather general. The information extracted by the inspector is the information relevant to whether or not a point is in the target. That information will take different forms depending on the search, it may be a fitness value, a probability, a yes/no answer, etc.
The authors of the paper conclude that Dieb’s objections derive from misunderstanding our paper. Despite five blog posts related to this paper, we find that Dieb has failed to raise any useful or interesting questions. Should Dieb be inclined to disagree with our assessment, we suggest that he organize his ideas and publish them as a journal article or in a similar venue.
57 Responses to Questioning Information Cost
Leave a Reply
You must be logged in to post a comment.
What would an organism have to do to explore the entire search space?
In other words, if a bacteria was to explore the entire search space, what would it have to do with its DNA every time it reproduced?
OT: Doug Axe weighs in on Darwin’s Doubt:
Answering Objections to Darwin’s Doubt from University of Texas Biologist Martin Poenie
Douglas Axe – July 12, 2013
http://www.evolutionnews.org/2.....74411.html
dmullenix, technically, individual organisms don’t explore search spaces. Its only the entire collection of organisms that can be considered to be performing a search. To explore the entire search of DNA sequences would mean that there was least one bacteria with each possible DNA. Of course, that’s far too vast to have actually occurred.
Winston Ewert, thank you for your post! I’ll address the five points in the following comments. I prepared my answer in this post at my blog, as using mathematical symbols doesn’t work here – therefore I’ll have to make some simplifications.
Firstly: Fair enough. So it’s not a quasi-Bayesian calculation, but a Bayesian quasi-calculation. I will amend my post (Please show all your work for full credit…) by Winston Ewert’s explanation.
Secondly:The problem is that Dembski’s, Ewert’s and Marks’s construction of the representation does not only depend on the discriminator (see the next point), but on the target, too. Take Omega = {1,2,3,4} and two searches with two steps:
1) The first search consist just of two random guesses, i.e., at each step, one of the numbers is given with probability 1/4.
2) The second search has two guesses, too. But at the first step, 1 is taken with probability 7/16 and each other number with 3/16, while at the second step, one is omitted from the guess and each other number it guessed with a probability of 1/3.
These two searches are quite different: the first may produce a query (1,1) with probability 1/16, while the second never will. Now take a discriminator which returns the target if it is in the query and otherwise another element in the query at random. Such a discriminator seems to be quite natural and it is certainly within the range of the definition on pages 35 – 36.
Now, the distribution which our discriminator infers on the search-space depends on the target: if we are looking for {1}, we get:
1) First search: measure mu given by mu{1}=7/16, mu{2}=mu{3}=mu{4}=3/16
2) Second search: a measure nu which is equal to mu.
These are two algorithms which don’t derive the same queries albeit in different ways, but nonetheless they will be represented the same way!
In fact, if our target is {2}, we get other distributions:
1) First search: measure mu given by mu{1}=7/16, mu{2}=mu{3}=mu{4}=3/16
2) Second search: measure nu given by nu{1}=14/96, nu{2}=44/96, nu{3}=nu{4}=19/96.
Frankly, this seems to be “inherently problematic”.
Thirdly: This seems to be a little absurd. Shouldn’t your representation work for any discriminator – even a good one? If we are following Wolpert’s and Macready’s formulation, a blind search means that we try to maximize a characteristic function. So, the natural discriminator should return this maximum if it is found in a query. If it doesn’t, we build a discriminator which does: we have the output of the inspector, so why not use it? If you are telling us that the output of the inspector may be false, then I’d use another inspector, one which gives us the output of the fitness function. If you say now that the output of the fitness function may be dubious, I’d say “tough luck: I maximize this function whether the function is right or wrong – what else is there to do?”. These added layers of entities which have a hidden knowledge about the target which isn’t inherent to the fitness function seem to be superfluous.
Fourthly: So, what is the difference between the inspector and the navigator? The navigator may take the output of the inspector into account, but nonetheless one could conflate both into a single pair of values – especially as you allow “different forms” for the inspector. So you could get rid of the third row of the search matrix.
Fiftly: Sorry, I may have been confused by the phrase “The inspector is an oracle that, in querying a search-space entry, extracts information bearing on its probability of belonging to the target “: if we look at the Dawkins’s Weasel and take the Hamming-distance as the fitness function, each returned value other than 0 tells us that the probability of belonging to the target T for an element is zero itself, whether it is “METHINKS IT IS LIKE A WEASER” or “AAAAAAAAAAAAAAAAAAAAAAAAAAAA”. I understand that you want to avoid the notion of proximity to a target, but your phrasing is misleading, too. Have you any example of a problem where the inspector returns a probability other than 0 or 1? In your examples, it seems to be always the output of a fitness function.
Conclusion: It’s always possible that I’ve misunderstood certain aspects of the paper. I would be grateful if you helped to clear up such misunderstanding. I hope that my comments above count as useful and at least a little bit interesting. I’m preparing an article, as I’ve promised earlier, but the work is quite tedious, and any clarification of the matters above. Furthermore, I’d like to know whether this “general framework” is still in use, or whether you have tried another way of representing searches as measures. Again, thank you Winston Ewert!
Correction: comment #6 titled “Secondly” has a wrong first line in the second enumeration. Instead of
1) First search: measure mu given by mu{1}=7/16, mu{2}=mu{3}=mu{4}=3/16
it should read:
1) First search: measure mu given by mu{2}=7/16, mu{1}=mu{3}=mu{4}=3/16
My apologies for this obvious error.
Hi, Winston –
Just a quick off-topic post: I was glad to see that you left a message on my TSZ response to your EnV piece. I was hoping you would respond at some stage to my post itself (and I apologise for initially mis-spelling your name).
Here is the link:
The eleP(T|H)ant in the Room
DiEb,
On the second point, as modelled in the paper, if your distribution shifts depending on the target, than you have different searches for different targets. Searches are not allowed to depend on the target, you have to pick a search using your knowledge of the target.
On the third point, this a search for a search. We are picking a search at random. As a result we may get a good discriminator and we may get a terrible one. Yes, if we assume that we have a good discriminator, we are going to get searches biased towards the target. However, that is not the scenario that the result is considering.
On the fourth point, the inspector and navigator are a division of the traditional fitness function into information relating to whether the current point is in the target and information relating to where to look for points in the target.
On the fifth point, consider defining the target to be the maximum of the fitness function. Since the maximum is unknown, we don’t know for certain whether a particular point is in the target. So we can’t represent it as a 0 or 1.
From my perspective, points 2 and 3 suggests you’re trying to make search for search into something it is not. Points 4 and 5 are essentially that you wouldn’t have modelled it that way, and thus not very serious as actual objections.
I look forward to seeing a published version of your thoughts.
Winston Ewert
Elizabeth Liddle,
Patience.
Winston Ewert
No problem, Winston!
I have a plenty of patience if I know there is a good probability that it will be rewarded!
Thanks.
Hi Winston,
Off topic, but I’m curious. Are you related to Donald Ewert?
ad 2:
A good search algorithm should provide different searches for different targets. This is possible as the fitness function is an element of a set of fitness functions – Dawkins’s WEASEL works with a Hamming-distance to METHINKS*IT*IS*LIKE*A*WEASEL and with a Hamming-distance to AAAAAAAAAAAAAAAAAAAAAAAAAAAA, finding the different strings. But that withstanding, I have given you two searches for the element {1} which are quite different, but are represented by the same measure. Any thoughts on that?
ad 3: Where in the paper do you state that the discriminator is picked at random, too?
ad 4:
I don’t see any reason for doing so – especially as you have the discriminator, too. But of course you are free to do so.
ad 5: There are problems where the extreme value of the fitness function is not known – like the TSP. OTOH you have problems with known values for the fitness function: blind search, where the function takes the values 0 or 1, or Hamming-distances. The example I gave allowed us to know whether the point is in the target (Hamming-distance 0) or not (Hamming-distance bigger than 0).
Keiths,
There is no known relation.
Winston Ewert
Dieb,
2) This is the search for a search, not the search for a search algorithm. The search consists of both the algorithm and whatever fitness function or equivalent. Your two Dawkins examples are two different searches, even if they have the same search algorithm.
You haven’t given me any reason to suppose that searches making different queries yet being represented by the same distribution is problematic. Me and you might both be represented as male for certain purposes. (I assume that Di… is a male name). That doesn’t pose any problem for anything.
3) The search is defined to be a six-tuple consisting of the initiator, terminator, inspector, navigator, nominator, and discriminator. The paper studies the question of picking a search at random, and that would imply picking each of the six components at random. We did not consider it necessary to specifically state that each individual component was also selected at random. That would seem to be implied.
4) Certainly, searches can be modelled without that feature. After all, we are arguing that we can model the entire search as just a probability distribution.
5) You asked for a case where the result wasn’t 0 or 1 for the inspector. I provided one.
Winston: this is a non-mathematical question, but I think it is pertinent:
What makes you think that all searches are equiprobable?
Or, alternatively, that any space in which not all searches are equiprobable must be the product of design?
Because it seems to me that this is an unsafe assumption. For example, to take a trivial example: water will reliably find a way from a hilltop to the ocean , even though there are many obstructions in the way. This isn’t because the water knows in advance where the ocean is, or that it even gets feedback as to whether it’s getting closer or not. The search is simply a function of the physical landscape itself.
Now you could argue, and I think Dembski sort of does, that ultimately, the landscape itself is only one of many equiprobable landscapes, including landscapes in which there is simply no exit to the ocean and the water simply evaporates in situ, as in saltpans and inland seas.
And perhaps, therefore, the “search for a search” extends right back to the search for a life-generating universe.
But at that point, the “universal probability bound” ceases to apply. We have no idea of the configuration space of life-generating universes, and certainly no citable figure or 10^150 possible events since the beginning of this one.
So in what sense does the Search for a Search argument have any bearing on the question of Design? Is it not possible that, given the universe we have, with the properties it has, that life-generating searches are probable enough to have a decent chance of occurring?
2) Though “representation” is not a defined term in maths, mathematicians have some expectations when this term is used: especially it should be possible to draw conclusions from the representation about the represented object. In my comment #6 I have shown that there are two quite different searches (in your sense) which are represented by the same measure. Any thoughts on that?
3) Do you really want to go there: each six-tuple is picked at random and than projected by its own discriminator into the space of measures? Frankly, than nothing of a representation is left! Is this your intention?
5).
Not exactly – I asked: “Have you any example of a problem where the inspector returns a probability other than 0 or 1?”
Addendum: Wouldn’t it be nice to look a class of “searches” which use the same terminator and the same discriminator?
DiEb,
2) Yes, you have defined two searches represented with the same measure. There is no dispute about that. However, I still have no idea why you think that’s a problem. You say, “it should be possible to draw conclusions from the representation about the represented object.” But I can draw conclusions about the represented object. I can conclude how often it hits my target. Thats the question we are interested in. If I wanted to answer other questions, I’d have to pick a different representation.
3) The paper itself says that the framework only comes up to show that we can represent searches by measures. So yes, the whole thing does collapse into a measure. That’s the whole point of the section.
5) If you want example of a probability, we can consider a case where we have noisy queries. Each query is the true value +/- some noise. The actual fitness value would allow us to calculate the probability of being in a target.
Addendum) Sure. We didn’t, but that would be an interesting area of research.
Elizabeth Liddle,
Fair question, but not one that is best dealt with in blog comments. I’m happy to clarify simple misunderstandings such as the case of DiEb here, but for serious discussion of the arguments, I think this is a very poor venue. I’m afraid I’ll have to ask for more patience.
Winston Ewert
No problem, Winston.
I have given you posting rights at my blog if you would like to write an OP there.
Elizabeth:
Unless that water is part of the Okavanga River.
2) How do you get back from the representation to the represented objects? If you have a set of searches which are mapped to a certain measure, how do you construct this set if the measure is given? If it is a “representation”, you should be able to do so.
3) When I hear “collapsing”, I’ve difficulties to think of a “representation”.
5) Again, you don’t give probability, but the output of a random variable. But I won’t pursue this matter.
Thank you for trying to clarify my simple misunderstandings of your theory. Here is another one:
So, lets take a finite search space with N elements. We are looking for a single element, so we try to maximize its characteristic function f. To keep everything finite, we don’t allow repetitions, i.e., in our search each place can only be visited once. This is – as Macready and Wolpert observed – always possible by keeping a look-up table and thus doesn’t change the set-up. Therefore, our search is completed in at most N steps.
(BTW: The claim that “each of the six components [is picked] at random” seems not to apply to the inspector: this is a fixed function for a search – in our case, the inspector returns the value of the fitness function. Of course, you can say that we pick the inspector at random out of the set of the one possible inspector.)
Let’s take a look at all the searches which are ended by their terminator only after the N-s step, i.e., the subset of all exhaustive searches. The price question: What is the probability to find the target in such an exhaustive search? Until now, everyone looking at such problems would have thought that this probability is one: we certainly visited the target and spotted that the function f takes it maximum there. But in the world of Dembski, Ewert, and Marks it is not, as a random discriminator takes its toll – and discriminators aren’t obliged to return the target if it was found and identified…
Counterintuitive? That is a flattering description: the discriminator’s purpose seems to be to turn even a search which is successful by all human standards into a guess to fit the idée fixe that each search can be “represented” by a measure on the search space
Addendum: If we wish to eliminate the condition of not having repetitions in our searches, we can observe just those searches which are terminated only after the whole search space was visited: terminators with this property exist. Such searches may have length N, but can be much longer. The result is the same: the probability of finding the target during a complete enumeration of the search space is (much) less than one. I have to ask: What good is a model in which an exhaustive search doesn’t fare much better than a single guess?
DiEb,
A representation is a many-to-one mapping from real world objects to mathematical representations. Many real world objects will be collapsed into one mathematical objection. It won’t, in general, be possible to go from the mathematical object to the real world object. You are objecting to properties that every representation has.
I’ve explicitly stated that all six components are chosen randomly. Why in the world would you decide that I didn’t really mean that the inspector was chosen randomly? Even exhaustive search requires access to some information about the target. You’ve got to at least have the ability to determine whether a point is in the target. NFL assumes that you have that, but S4S does not.
An exhaustive search will fare better than a random guess. But we are searching for a search. We are picking a search from all possible searches. Exhaustive search is much better than a random guess, and by the consequence of the paper’s results much rarer.
I’m finished with this discussion, DiEb. You’ve still failed to raise any interesting questions or demonstrate comprehension of what the paper is doing. What’s more, you’ve chosen to accuse us of bad faith, which is a sign of someone looking to find fault rather than understand. As iterated in my post, if you want responses from us on your ideas, you are going to have to publish them.
a) Generally I think it is nice that you know about which specific real world objects you draw the conclusions when you are looking at the representation. But that may be just a personal preference.
b) How in the world do you choose the inspector at random? You have the output of an oracle, or a fitness function, or this guy who shouts warmer and colder. In all of these cases a complete enumeration discloses the optimum. The S4S should work in these cases, too.
c) “An exhaustive search will fare better than a random guess.” No, not really, not in your framework, not after you have applied a random discriminator to the search matrix of an exhaustive search.
d) “I’m finished with this discussion, DiEb. You’ve still failed to raise any interesting questions or demonstrate comprehension of what the paper is doing.” I agree that some of the questions aren’t very interesting, but they seem to be helpful. “What’s more, you’ve chosen to accuse us of bad faith” I’m quite critical of your work, but I do believe that you stand behind your mathematics, and I take it as a sign of good faith that you are willing to help your readers to understand the paper.
DiEb,
I guess I wasn’t finished.
When you say things like that it would be flattering to describe our work as counter-intuitive, I take that as an accusation of bad faith. Perhaps it was not intended as such.
It seems that two things have gotten conflated here. There are two questions. Firstly, can all searches be represented as a probability measure? Secondly, if we pick randomly from all searches is that equivalent to picking uniformly over all probability measures?
When I say that you pick the components of the search randomly, I’m only referring to answering the second question. That has nothing to do with the answer to the first question. A search can be modelled as a probability distribution regardless of your choice of the search components.
If I’m studying a particular search, such as exhaustive search or easter egg search, I’m not picking the components at random. Picking the components at random is brought up in response to your objection that the discriminator should bias the search towards the target. It was not intended to answer your objection that a search cannot be represented as a probability measure.
As for a search being represented as a probability measure: the search is defined to include both the fitness function and the search algorithm. Together, these clearly form a stochastic process with no external inputs. Thus, the search can be represented as a probability distribution over the search space.
WE: It seems that in many relevant cases, exhaustion of the space is not possible on accessible resources, a key point in design related issues. It means that unless a search is aided by an oracle or the like, it is overwhemingly unlikely to succeed, once relevant target zones are sufficiently rare. KF
OT: Darwin as the Pinball Wizard: Talking Probability with Robert J. Marks II
http://www.youtube.com/watch?v=Kxv3Q0VaX9E
General Remark: I got the impression that there aren’t many mathematicians out there who won’t dismiss your work out of hand, but are willing to read your texts, follow your calculations, and really try to understand what you are doing. When this text was presented in Ithaca, how many mathematicians were there in the audience? Were the mathematics discussed, or only the philosophical implications? Compare this situation to 2010, when Vinay Deolalikar proposed his proof on N != NP: you had an instant buzz in the blogosphere, , a back and forth of arguments, and at the end of it all, everyone involved could write a paper
This thread is the first one I have seen in which the mathematical content of the article is discussed, and even here, at the blog founded by William Dembski himself, only very few commentators have actually read the article. True, I’m very critical when it comes to the work of the EIL, but I’m eager to discuss it. You don’t have to be thrilled by this, but surely, you must see the opportunity: at the end of the day, at the very least we should be able state our arguments more clearly.
Indeed, I think your framework can be worse than counterintuitive: at the moment, I’m inclined to say that it is not even very useful. But perhaps, you will change my mind.
Winston Ewert, perhaps you can clarify the following point:
If you look at the literature, you will find that search problems are seen as a special case of optimization problems: you have a cost function, and you try to find its optimum. Sometimes you are interested only in the value of the optimum, sometimes you are interested in the place where this optimum occurs – than you have a search. The main point is: if you have found the optimum, you have solved the problem – the X marks the spot.
Such a cost function can be straight forward – take e.g. f being the Hamming distance to “BOB”. It can be misleading: let g be the Hamming distance to “TIM”, but set g(“TIM”)=3 and g(“BOB”)=0. What are we looking for? Right, again for “BOB”.
Am I right to think that you have separated the cost function from the search problem? You seem to allow for an unaltered g, the Hamming distance to “TIM” while in reality searching for “BOB”. If you do so, it becomes very difficult to compare your results with anything of the classical theories.
Indeed, take exhaustive searches which are identical in their first five components, but differ in their “discriminator”. It is quite baffling that such searches will be “represented” by quite different measures giving all probabilities for hitting the target between 0 and 1, while every performance measure in the sense of Macready and Wolpert will have the same result on these searches.
Can we exemplify this? Let’s look for a single element in a small set – let’s say for the element 1 in the set of four elements {1,2,3,4} and let’s say that the fitness function is just the characteristic function of the element 1 and that that is all we know. Then:
1) The “initiator” is a random variable taken values in {1,2,3,4}
2) The “terminator” is a randomly chosen stopping time for the stochastic process given by the search
3) The “inspector” is the output of the fitness function – or are there any alternatives to choose from?
3) The “navigator” doesn’t come into play, as no additional knowledge is assumed
4) The “nominator” is again randomly chosen
5) The “discriminator” is a random variable taken values in the output of the stopped process.
Am I correct so far?
DiEb,
Yes, as you’ve put it we have separated the cost function from the search problem. It’d be possible to run a hamming search for FOO when you really wanted BAR.
I fail to see why that’s baffling. Obviously, there are possible searches with poor discriminators. Actually there is a paper, “Some multiobjective optimizers are better than others” which looks at a case of that. (Of course, they aren’t calling it a discriminator).
Are you correct so far? I’m not sure what you are trying to do. Are you trying to pick a random search? Are you trying to model a particular search?
“I fail to see why that’s baffling.” It is baffling as your group is the only one who does so. Everyone else is trying to find the optimum of the fitness function – or in the case of multiobjective optimizers – a set of non-dominated points (as David Corne’s and Joshua Knowles’s do in the paper you have mentioned).
If you look into paper, you will see that in the case of one-dimensional optimization the archive will always contain the best element found so far, so at the end of the search it will return just the element with the best fitness value in your search matrix (to quote Corne and Knowles: “The archive plays the role of the ‘best so far’ placeholder in single objective optimisation. However, whereas in single- objective optimisation it is entirely trivial to maintain this best-so-far record, the story is quite different in multiobjective optimisation.”)
So when we are talking about “single objective optimisation” – as in finding the maximum of a characteristic function – there is exactly one possible archiver, though there is a abundance of discriminators.
What am I trying to do? I want to describe the set of all possible searches for a single element out of a set of four elements. According with the general thought, this means that I want to maximize the characteristic function of that element. But I get the impression that that isn’t the case in your framework as you state that you ” have separated the cost function from the search problem”).
DiEb,
Yes, as far as I know we are the only group who considers searches with counter-productive discriminators. The Corne paper discuss archives of varying quality but assumes a “precise” archiver. However, searches without precise archives and counter-productive discriminators exist and thus I think our model should be able to accommodate them.
Right, to describe the set of all possible searches, you’d have to be randomly choosing the inspector from the set of possible inspectors which may or may not correlate with your target. As I’ve tried to express, access to the characteristic function (or fitness function) is not assumed when picking a search at random.
1) In all the “single objective optimisation” problems, the archiver will return the best so far value, whether the archiver is precise or not. There is nothing to accommodate: the quote which I gave above is meant for all kinds of archives. Again: archives are not as random as discriminators, as they are biased toward good values – even archives which are not precise.
2) The whole thing becomes a little bit to random for my taste: who knows what the target is? The discriminator may have this knowledge – or may not have it. Where is the objective criterion of having met the target? Where is it formalized? If I have minimized the cost function with FOO, who will tell me that I was indeed looking for BAR? If this game is played at the village fair, you will have a brawl in no time, accompanied by accusations of cheating!
3) You said “An exhaustive search will fare better than a random guess.” How so? On average, it will not, it will be as bad as a random guess.
1) They define an archiver as a mapping: A_N x Z -> A_N. Its a perfectly valid archiver to map everything to the empty archive. It is only the precise requirement that makes it keep the best point in memory on the single objective case.
Your quotes states that archives play the role of the best-so-far record. They are effectively a generalization of best-so-far records. It states that maintaing a best so far record is trivial, but no statement that an archiver will maintain a correct best-so-far record.
But I’m not disputing that the discriminator is more random than the archiver. The discriminator gives the algorithm more leeway than an archiver. My point is merely that we are taking what was done there but going further with it.
2) The framework defines the target as being a subset of the search space. It is assumed to be a given. A search succeeds if it picks a point which is in the target. So the target is assumed to be defined before you start analyzing the search. It is not some sort of unknowable.
The target is known to person analyzing the search, but it may or may not be know to the search itself.
1) An archiver in a “single objective optimisation” “plays the role of the ‘best so far’ placeholder”, too – so it is the ‘best so far’ placeholder. There is nothing arbitrary about this in this case. Yes, it is a map A_N x Z -> A_N, but in the case of the “single objective optimisation”, the map is fully characterized by its role. So I don’t think that you are going further, your discriminator and the archive are only loosely related.
2) The target plays is not unimportant in your concept: you should formalize it: “The target is known to person analyzing the search, but it may or may not be known to the search itself” doesn’t fit well into your 6-tuple approach.
DiEb,
Please read the start of section 2 of the paper again. It’s pretty clear that we do formalize the target.
The fact that you choose to ignore that we’ve done so and continue to insist on restrictions to archivers that the authors of that paper never do has left me too frustrated with to continue this discussion.
1) Indeed, at the begin of section 2 you state “Let T = {\omega_1, \omega_2, \dots, \omega_k} be the target and define the probability p = K/N.” So I’ve been imprecise when I implied that the target isn’t formalized in your framework – I do apologize. I’m afraid that readers who are familiar with the definitions of, e.g., Wolpert and Macready, will approach you framework with a similar misconception that I had, and interpret the sentence “The inspector O_{\alpha} is an oracle that, in querying a search-space entry, extracts information bearing on its probability of belonging to the target T” in a way that the inspector is somewhat depending on T – as it is in the the usual definition as being the place where the cost function take its optimum, while in your framework it can be fully independent of T. When I asked for a formalization, I meant that I’d appreciated that this independence is stressed in your phrasing of the framework.
2) As for the article of Corne and Knowles: my reading of the text differs from yours. That can happen. I think that there are various possible archives in the case of a “multiobjective optimizer”, while in the single objective case, you don’t have much choice (and the archiver is unnecessary as it is trivial). It’s interesting that the authors choose as the usual performance measure in single objective optimisation “max(d_m^y) (assuming maximasation, of course)”. I’ll look for other papers of the authors to bolster this view (which must be a trivial point to them), and we always have the possibility to just ask the authors.
3) I hope that you change your mind about continuing this discussion: if it helps, I get sometimes frustrated, too. You have certainly cleared of some misconceptions which I hold about the framework!
Unfortunately, at this point of the discussion I’m left with the following conclusion:
In the general framework Of Dembski, Ewert, and Marks searches which have enumerated the complete search space will on average find the target with the same probability as a random guess.
1) Given your confusion on this point, I’ll be looking to emphasize this in future work.
2) Your reading makes no sense to me. You seem to be inventing a restriction on archivers that the authors do not state when they define them. Regardless, its not an important point here.
What makes you think that an exhaustive search succeeds only as often as a random guess?
1) Thanks, that will be appreciated by all those who share my confusion.
2) Well, it doesn’t matter really. And it doesn’t matter that the archive and the archiver are only tools which keep a small part of the sample path, as they are realizations of computational restrictions, while your discriminator works with the whole sample path / search matrix. For me, it’s a totally different animal, but we don’t have to go there.
3) What makes you think that an exhaustive search succeeds only as often as a random guess? That’s not exactly what I said: I’m stating that exhaustive searches will on average succeed only as often as a random guess. This average is taken over all inspectors and discriminators. Take for example a search which enumerates the elements \omega_1, \omega_2, \dots. The second line of your search matrix contains the output of the inspector: if this one is chosen randomly, any combination of values \alpha_1, \alpha_2, \dots, \alpha_N will occur with the same probability: in other words – the output is independent of the search and can be ignored.
At this point, we who we are performing the search, know nothing about the target: it could be FOO, it could be BAR
But now comes the random discriminator. If it has no “independent knowledge”, it has to perform a random search on the search matrix, thereby being as good a a random guess.
If it has “independent knowledge”, i.e., if it returns the target “with greater certainty than is possible simply on the basis of the information delivered by the inspector and the navigator”, than we can combine it with a permutation of the elements of \Omega to get another discriminator which prefers another element. If we take the average over all permutations, everything levels out, and we are again left with a random guess.
What is quite irritating in the scenario above: For each element \mu in M(\Omega) you can take our enumeration, have a random inspector and then find a discriminator which maps our exhaustive search onto this \mu…
————
What is quite irritating in the scenario above: For each element μ in M(Ω) you can take our enumeration, take a random inspector and then find a discriminator which maps our exhaustive search onto this μ…
No. No. No. You only take the average over all inspectors and discriminators if you are picking a search at random. If you are performing an exhaustive search you aren’t picking a search at random.
Sorry, but if I pick a search at random out of the subset of the exhaustive searches, I end up with a search which does exactly as good as a random guess. That’s quite different from Macready’s and Wolpert’s ideas…
DiEb,
Yes. If you pick a random inspector/discriminator you are going to get the equivalent of a random guess regardless of the rest of your search.
And?
Yes, that’s different from previous work. But we are not inconsistent with those results. We are just considering more cases.
Quoting from the paper:
The authors simply assert that the process of cumulative variation and selection is a targeted search, when this is not how evolutionary biologists portray evolution (I note that a comment in a popular book written thirty years ago is not the only evidence that exists indicating that evolution stumbles upon viable solutions near to already viable solutions to earning a living). I wonder whether arguing about whether the mathematical model works is rather premature. Should we not first be convinced that the model presented is at all appropriate.
Exactly, Alan. This all seems a little like shifting deckchairs on the Titanic to me.
A static search space with a static target and static feedback seems a very odd way to simplify evolutionary optimisation. It seems to me that the very things that make it so powerful have been simplified out.
The thing about evolution is that it isn’t a search for a hidden target at all, or even several hidden targets. It’s a search for solutions – any solutions – to the problem of persisting in the current environment, and that environment, both its resources and threats, will change as a function of the solutions found. So for a start it is massively non-linear.
I think if the “evolutionary informatics” lab are going to do “evolutionary informatics” they need a better model of evolutionary optimisation.
Lizzie,
That assumes that the folks at the EIL are actually trying to model evolution, versus caricaturing it.
As to accurately trying to model evolution, versus caricaturing it, this is the best program thus far developed trying to accurately model evolution:
Of course Darwinists deceptively deny that this computer model which uses realistic parameters has anything to do with Darwinism, but what type of honesty should we expect from people who deceptively claim that intelligently designed computer algorithms provide convincing proof for unguided Darwinian evolution in the first place?
In the following podcast, Dr. Robert Marks gives a very informative talk as to the strict limits we can expect from any evolutionary computer program (evolutionary algorithm):
Darwin as the Pinball Wizard: Talking Probability with Robert J. Marks II – video
http://www.youtube.com/watch?v=Kxv3Q0VaX9E
7:00 minute mark
“For many years I thought that it is a mathematical scandal that we do not have a proof that Darwinian evolution works.”
Gregory Chaitin – Proving Darwin 2012 – Highly Respected Mathematician
Elizabeth:
What is “evolutionary optimization”? Natural selection doesn’t optimize, so please do tell what you are talking about.
BTW Lizzie, unguided evolution isn’t a search at all. It’s more like a drunk stumble. Ya see blind and undirected processes cannot search and that is what darwinian and neo-darwinian evolution posits.
keiths:
No one can model unguided evolution, not even evolutionary biologists.